perm filename QUEENS.FAI[1,BGB] blob sn#057498 filedate 1973-08-10 generic text, type T, neo UTF8
COMMENT ⊗   VALID 00010 PAGES 
RECORD PAGE   DESCRIPTION
 00001 00001
 00003 00002	TITLE QUEENS PUZZLE PROBLEM  -  1 DECEMBER 1972.
 00005 00003	TABLES OF THE GROUP OF SYMMETRIES OF A SQUARE.
 00007 00004	T4:
 00009 00005	One Queen Attack Table  -  64 boards.
 00011 00006	MAKE ONE QUEEN ATTACK TABLE.
 00013 00007	MAKE TWO QUEEN ATTACK TABLE - UNORDERED PAIR OF QUEENS.
 00014 00008	MAKE FIVE QUEEN ATTACKS - RECORD FULL BOARD COVERAGE.
 00016 00009	IGNORE REDUNDANT SOLUTIONS DUE TO BOARD SYMMETRIES.
 00018 00010	MAIN EXECUTION.
 00019 ENDMK
⊗;
TITLE QUEENS PUZZLE PROBLEM  -  1 DECEMBER 1972.

;ACCUMULATORS

	Q1←7
	Q2←10
	R←11	↔	ROW←12
	C←13	↔	COL←14
	K←14
	CNT←15
	I←16
	J←17

; ALTERNATE PDP-10 MNEMONICS.

	OPDEF LIP[HLR]↔OPDEF LAP[HRR]↔OPDEF DIP[HRLM]
	OPDEF DAP[HRRM]↔OPDEF CAR[HLRZ]↔OPDEF CDR[HRRZ]
	OPDEF DIPZ[HRLZM]↔OPDEF DAPZ[HRRZM]↔OPDEF ZIP[HRRZS]
	OPDEF ZAP[HLLZS]↔OPDEF WIP[HRROS]↔OPDEF WAP[HRRZS]
	OPDEF NIP[HLRE]↔OPDEF NAP[HRRE]↔OPDEF NIM[HRREI]
	OPDEF LAC[MOVE]↔OPDEF DAC[MOVEM]↔OPDEF SLAC[MOVS]
	OPDEF GO[JRST]↔OPDEF LACI[MOVEI]↔OPDEF SLACI[MOVSI]
	OPDEF LAPI[HRRI]↔OPDEF LIPI[HRLI]↔OPDEF LACN[MOVN]

;YE VERY OLDE TYPE OUT DECIMAL NUMBER ROUTINE.

ONUM:	IDIVI 1,12↔PUSH 17,2↔SKIPE 1↔PUSHJ 17,ONUM
	POP 17,1↔ADDI 1,60↔OUTCHR 1↔POPJ 17,

PDL:	BLOCK 100
;TABLES OF THE GROUP OF SYMMETRIES OF A SQUARE.


;T0:
	;00 ;01 ;02 ;03 ;04 ;05 ;06 ;07 
	;10 ;11 ;12 ;13 ;14 ;15 ;16 ;17 
	;20 ;21 ;22 ;23 ;24 ;25 ;26 ;27 
	;30 ;31 ;32 ;33 ;34 ;35 ;36 ;37 
	;40 ;41 ;42 ;43 ;44 ;45 ;46 ;47 
	;50 ;51 ;52 ;53 ;54 ;55 ;56 ;57 
	;60 ;61 ;62 ;63 ;64 ;65 ;66 ;67 
	;70 ;71 ;72 ;73 ;74 ;75 ;76 ;77 

T1:	 
	 07 ↔06 ↔05 ↔04 ↔03 ↔02 ↔01 ↔00 
	 17 ↔16 ↔15 ↔14 ↔13 ↔12 ↔11 ↔10 
	 27 ↔26 ↔25 ↔24 ↔23 ↔22 ↔21 ↔20 
	 37 ↔36 ↔35 ↔34 ↔33 ↔32 ↔31 ↔30 
	 47 ↔46 ↔45 ↔44 ↔43 ↔42 ↔41 ↔40 
	 57 ↔56 ↔55 ↔54 ↔53 ↔52 ↔51 ↔50 
	 67 ↔66 ↔65 ↔64 ↔63 ↔62 ↔61 ↔60 
	 77 ↔76 ↔75 ↔74 ↔73 ↔72 ↔71 ↔70 

T2:
	 70 ↔71 ↔72 ↔73 ↔74 ↔75 ↔76 ↔77 
	 60 ↔61 ↔62 ↔63 ↔64 ↔65 ↔66 ↔67 
	 50 ↔51 ↔52 ↔53 ↔54 ↔55 ↔56 ↔57 
	 40 ↔41 ↔42 ↔43 ↔44 ↔45 ↔46 ↔47 
	 30 ↔31 ↔32 ↔33 ↔34 ↔35 ↔36 ↔37 
	 20 ↔21 ↔22 ↔23 ↔24 ↔25 ↔26 ↔27 
	 10 ↔11 ↔12 ↔13 ↔14 ↔15 ↔16 ↔17 
	 00 ↔01 ↔02 ↔03 ↔04 ↔05 ↔06 ↔07 

T3:
	 77 ↔76 ↔75 ↔74 ↔73 ↔72 ↔71 ↔70 
	 67 ↔66 ↔65 ↔64 ↔63 ↔62 ↔61 ↔60 
	 57 ↔56 ↔55 ↔54 ↔53 ↔52 ↔51 ↔50 
	 47 ↔46 ↔45 ↔44 ↔43 ↔42 ↔41 ↔40 
	 37 ↔36 ↔35 ↔34 ↔33 ↔32 ↔31 ↔30 
	 27 ↔26 ↔25 ↔24 ↔23 ↔22 ↔21 ↔20 
	 17 ↔16 ↔15 ↔14 ↔13 ↔12 ↔11 ↔10 
	 07 ↔06 ↔05 ↔04 ↔03 ↔02 ↔01 ↔00 

T4:
	70 ↔60 ↔50 ↔40 ↔30 ↔20 ↔10 ↔00 
	71 ↔61 ↔51 ↔41 ↔31 ↔21 ↔11 ↔01 
	72 ↔62 ↔52 ↔42 ↔32 ↔22 ↔12 ↔02 
	73 ↔63 ↔53 ↔43 ↔33 ↔23 ↔13 ↔03 
	74 ↔64 ↔54 ↔44 ↔34 ↔24 ↔14 ↔04 
	75 ↔65 ↔55 ↔45 ↔35 ↔25 ↔15 ↔05 
	76 ↔66 ↔56 ↔46 ↔36 ↔26 ↔16 ↔06 
	77 ↔67 ↔57 ↔47 ↔37 ↔27 ↔17 ↔07 

T5:
	77 ↔67 ↔57 ↔47 ↔37 ↔27 ↔17 ↔07 
	76 ↔66 ↔56 ↔46 ↔36 ↔26 ↔16 ↔06 
	75 ↔65 ↔55 ↔45 ↔35 ↔25 ↔15 ↔05 
	74 ↔64 ↔54 ↔44 ↔34 ↔24 ↔14 ↔04 
	73 ↔63 ↔53 ↔43 ↔33 ↔23 ↔13 ↔03 
	72 ↔62 ↔52 ↔42 ↔32 ↔22 ↔12 ↔02 
	71 ↔61 ↔51 ↔41 ↔31 ↔21 ↔11 ↔01 
	70 ↔60 ↔50 ↔40 ↔30 ↔20 ↔10 ↔00 

T6:
	00 ↔10 ↔20 ↔30 ↔40 ↔50 ↔60 ↔70 
	01 ↔11 ↔21 ↔31 ↔41 ↔51 ↔61 ↔71 
	02 ↔12 ↔22 ↔32 ↔42 ↔52 ↔62 ↔72 
	03 ↔13 ↔23 ↔33 ↔43 ↔53 ↔63 ↔73 
	04 ↔14 ↔24 ↔34 ↔44 ↔54 ↔64 ↔74 
	05 ↔15 ↔25 ↔35 ↔45 ↔55 ↔65 ↔75 
	06 ↔16 ↔26 ↔36 ↔46 ↔56 ↔66 ↔76 
	07 ↔17 ↔27 ↔37 ↔47 ↔57 ↔67 ↔77 

T7:
	07 ↔17 ↔27 ↔37 ↔47 ↔57 ↔67 ↔77 
	06 ↔16 ↔26 ↔36 ↔46 ↔56 ↔66 ↔76 
	05 ↔15 ↔25 ↔35 ↔45 ↔55 ↔65 ↔75 
	04 ↔14 ↔24 ↔34 ↔44 ↔54 ↔64 ↔74 
	03 ↔13 ↔23 ↔33 ↔43 ↔53 ↔63 ↔73 
	02 ↔12 ↔22 ↔32 ↔42 ↔52 ↔62 ↔72 
	01 ↔11 ↔21 ↔31 ↔41 ↔51 ↔61 ↔71 
	00 ↔10 ↔20 ↔30 ↔40 ↔50 ↔60 ↔70 
;One Queen Attack Table  -  64 boards.
	QAT1:	BLOCK =64
	QAT2:	BLOCK =64

;Two Queens Attack Table  -  2016 boards.
	QQAT1:	BLOCK =2016
	QQAT2:	BLOCK =2016
	QQL1:	BLOCK =2016
	QQL2:	BLOCK =2016

;Scratch Attack Table - 2016 boards.
	SAT1:	BLOCK =2016
	SAT2:	BLOCK =2016
	SAT3:	0

;Column attack table - 8 boards.
CAT:	1001001001B28↔1001001001B28	;COL 0.
	1001001001B29↔1001001001B29	;COL 1.
	1001001001B30↔1001001001B30	;COL 2.
	1001001001B31↔1001001001B31	;COL 3.
	1001001001B32↔1001001001B32	;COL 4.
	1001001001B33↔1001001001B33	;COL 5.
	1001001001B34↔1001001001B34	;COL 6.
	1001001001B35↔1001001001B35	;COL 7.

;Row Attack Table - 8 boards.
RAT:	377B8↔0		;ROW 0.
	377B17↔0	;ROW 1.
	377B26↔0	;ROW 2.
	377B35↔0	;ROW 3.
	0↔377B8		;ROW 4.
	0↔377B17	;ROW 5.
	0↔377B26	;ROW 6.
	0↔377B35	;ROW 7.

;Byte pointer to column 7 of each row.
ROWPTR:	POINT 1,Q1,8 ↔ POINT 1,Q1,17	;ROWS 0 & 1.
	POINT 1,Q1,26↔ POINT 1,Q1,35	;ROWS 2 & 3.
	POINT 1,Q2,8 ↔ POINT 1,Q2,17	;ROWS 4 & 5.
	POINT 1,Q2,26↔ POINT 1,Q2,35	;ROWS 6 & 7.

;Byte pointer P-bits of each column.
COLPTR:	7B5↔6B5↔5B5↔4B5
	3B5↔2B5↔1B5↔0

;Make a bit pointer to a square of the board.
	DEFINE MKPTR{LAC 1,ROWPTR(R)↔ADD 1,COLPTR(C)}
;MAKE ONE QUEEN ATTACK TABLE.
MKQAT:	0
	LACI I,100↔LACI ROW,7↔LACI COL,7↔SOS I
	LSH ROW,1↔LAC Q1,RAT(ROW)↔LAC Q2,RAT+1(ROW)↔LSH ROW,-1
	LSH COL,1↔IOR Q1,CAT(COL)↔IOR Q2,CAT+1(COL)↔LSH COL,-1
	LACI 1
	LAC R,ROW↔LAC C,COL↔JSR NE
	LAC R,ROW↔LAC C,COL↔JSR NW
	LAC R,ROW↔LAC C,COL↔JSR SW
	LAC R,ROW↔LAC C,COL↔JSR SE
	LAC R,ROW↔LAC C,COL↔MKPTR↔SETZ↔DPB 0,1
	DAC Q1,QAT1(I)↔DAC Q2,QAT2(I)
	SOJGE COL,MKQAT+4
	SOJGE ROW,MKQAT+3
	GO @MKQAT

;NORTH EAST ATTACK: R-1,C+1.
NE:	0
	SOSGE R↔GO@NE
	AOS C↔CAIN C,8↔GO @NE
	MKPTR↔DPB 0,1↔GO NE+1

;NORTH WEST ATTACK: R-1,C-1.
NW:	0
	SOSGE R↔GO@NW
	SOSGE C↔GO@NW
	MKPTR↔DPB 0,1↔GO NW+1

;SOUTH WEST ATTACK: R+1,C-1.
SW:	0
	AOS R↔CAIN R,8↔GO@SW
	SOSGE C↔GO@SW
	MKPTR↔DPB 0,1↔GO SW+1

;SOUTH EAST ATTACK: R+1,C+1.
SE:	0
	AOS R↔CAIN R,8↔GO@SE
	AOS C↔CAIN C,8↔GO@SE
	MKPTR↔DPB 0,1↔GO SE+1

;MAKE TWO QUEEN ATTACK TABLE - UNORDERED PAIR OF QUEENS.
MKQQAT:	0
	SETZ I,
	SETZ 1,
L1:	SETZ 2,
L2:	CAML 1,2↔GO L3
	LAC QAT1(1)↔IOR QAT1(2)↔DAC QQAT1(I)
	LAC QAT2(1)↔IOR QAT2(2)↔DAC QQAT2(I)
	DAC 1,QQL1(I)
	DAC 2,QQL2(I)
	AOS I
L3:	AOS 2↔CAIE 2,100↔GO L2
	AOS 1↔CAIE 1,100↔GO L1
	GO @MKQQAT

;MAKE A PARTIAL THREE QUEEN ATTACK TABLE.
;ARGUMENT  -  THIRD QUEEN'S POSITION NUMBER  -  AC1.
MK3QAT:0
	LAC[XWD QQAT1,SAT1]↔BLT SAT3-1
	LAC Q1,QAT1(K)
	LAC Q2,QAT2(K)
	IOR Q1,[400400400400]	;SET EMPTY BITS.
	IOR Q2,[400400400400]
	LACI I,=2016
	IORM Q1,SAT1(I)
	IORM Q2,SAT2(I)
	SOJGE I,.-2
	GO @MK3QAT
;MAKE FIVE QUEEN ATTACKS - RECORD FULL BOARD COVERAGE.
MK5QAT:	0
	SETZ CNT,
	SETZ I,
M1:	SETZ J,
	CAML K,QQL1(I)↔GO M4
	LAC  0,QQL2(I)
M2:	CAML 0,QQL1(J)↔GO M3
	SETCM Q1,SAT1(I)↔ANDCM Q1,SAT1(J)↔JUMPN Q1,M3
	SETCM Q2,SAT2(I)↔ANDCM Q2,SAT2(J)↔JUMPN Q2,M3

;DETECT SOLUTIONS THAT ARE REDUNDANT BECAUSE THEY CAN BE
;MAPPED INTO A FORM WITH A QUEEN LESS THAN K.
	LAC 1,K↔LSH 1,6
	IOR 1,QQL1(I)↔JSR SYMM↔LSH 1,6
	IOR 1,QQL2(I)↔JSR SYMM↔LSH 1,6
	IOR 1,QQL1(J)↔JSR SYMM↔LSH 1,6
	IOR 1,QQL2(J)↔JSR SYMM

;DETECT SOLUTIONS THAT ARE REDUNDANT BECAUSE THEY MAP
;A QUEEN INTO POSITION K AND HAVE ALREADY BEEN RECORDED.
	JUMPE CNT,M5↔DAC 1,10
	JSR SYMM2↔ROT 1,-6
	JSR SYMM2↔ROT 1,-6
	JSR SYMM2↔ROT 1,-6
	JSR SYMM2↔LSH 1,-6
	JSR SYMM2↔LAC 1,10

;OUTPUT A SOLUTION TO THE BUFFER.
M5:	AOS 2,SUBTOTAL#
	AOS CNT
M0:	DAC 1,BUFFER(2)

M3:	AOS J↔CAIE J,=2016↔GO M2
M4:	AOS I↔CAIE I,=2016↔GO M1
	GO @MK5QAT

BUFFER:	BLOCK 5000
;IGNORE REDUNDANT SOLUTIONS DUE TO BOARD SYMMETRIES.
; π/2 ROTATIONS; DIAGONAL, HORIZONTAL & VERTICAL REFLECTIONS.
SYMM:	0
	LAC 2,1
	ANDI 2,77
	FOR @' I←1,7{
	CAMLE K,T'I(2)↔GO M3}
	GO@SYMM
SYMM2:	0
	LAC 2,1
	ANDI 2,77
	FOR @' I←1,7{
	CAMN K,T'I(2)↔JSP 12,SYMT'I}
	GO @SYMM2

;TRANSFORM THE SOLUTION IN AC-10.
	FOR @' I←1,7{
SYMT'I:
	LAC 11,[POINT 6,10,5]
	ILDB 3,11↔LAC 3,T'I(3)
	ILDB 4,11↔LAC 4,T'I(4)
	ILDB 5,11↔LAC 5,T'I(5)
	ILDB 6,11↔LAC 6,T'I(6)
	ILDB 7,11↔LAC 7,T'I(7)
	GO SYM3}

;GET THE TRANSFORMED SOLUTION INTO CANONICAL FORM.
SYM3:	CAML 3,4↔EXCH 3,4↔CAML 3,5↔EXCH 3,5
	CAML 3,6↔EXCH 3,6↔CAML 3,7↔EXCH 3,7
	CAML 4,5↔EXCH 4,5
	CAML 4,6↔EXCH 4,6↔CAML 4,7↔EXCH 4,7
	CAML 5,6↔EXCH 5,6↔CAML 5,7↔EXCH 5,7
	CAML 6,7↔EXCH 6,7

	LSH 3,6↔IOR 3,4↔LSH 3,6↔IOR 3,5
	LSH 3,6↔IOR 3,6↔LSH 3,6↔IOR 3,7

;SEARCH BACK THROUGH THE BUFFER FOR A MATCH.
	LAC 4,CNT↔LAC 5,SUBTOTAL
	CAMN 3,BUFFER(5)↔GO M3↔SOS 5
	SOJG 4,.-3↔GO(12)
;MAIN EXECUTION.
SA:	JSR MKQAT
	JSR MKQQAT
	SETZM TOTAL#

DEFINE CALLQ $(Q){
	LACI K,Q↔JSR MK3QAT↔JSR MK5QAT
	DAC CNT,CNT$Q#↔ADDM CNT,TOTAL
	JSR OUTNUM}
	
	CALLQ(23)
	CALLQ(22)
	CALLQ(13)
	CALLQ(12)
	CALLQ(11)
	CALLQ(03)
	CALLQ(02)
	CALLQ(01)
	CALLQ(00)

;OUTPUT FILE OF SOLUTIONS.
	LAC SUBTOTAL↔DAC BUFFER
	INIT 1,17↔SIXBIT/DSK/↔0↔HALT
	ENTER 1,[SIXBIT/QFILE/↔0↔0↔0]↔JFCL
	OUT 1,[IOWD 5000,BUFFER↔0]↔JFCL↔RELEASE 1,
	CALLI 12

OUTNUM:	0
	OUTSTR[BYTE(7)15,12]↔LACI 17,PDL
	LAC 1,CNT↔PUSHJ 17,ONUM↔OUTCHR[9]
	LAC 1,SUBTOTAL↔PUSHJ 17,ONUM↔OUTCHR[9]
	LAC 1,TOTAL↔PUSHJ 17,ONUM
	GO @OUTNUM

END SA